//LCR 114. 火星词典
class Solution {
public:
    string alienOrder(vector<string>& words) {
        unordered_map<char, unordered_set<char>> edges;
        unordered_map<char, int> in;
        string ret;

        for (auto& word : words)
            for (auto& ch : word)
                in[ch] = 0;

        int m = words.size();
        int n = words[0].size();
        for (int i = 0; i < m - 1; i++) {
            for (int j = i + 1; j < m; j++) {
                int k = 0;
                int i_str_size = words[i].size();
                int j_str_size = words[j].size();
                int temp = min(i_str_size, j_str_size);

                while (k < temp) {
                    if (words[i][k] != words[j][k]) {
                        char a = words[i][k];
                        char b = words[j][k];
                        if (edges[a].count(b) == 0) {
                            edges[a].insert(b);
                            in[b]++;
                        }
                        break;
                        //  goto  next;
                    }
                    k++;
                }
                if (k >= j_str_size && i_str_size != j_str_size)
                    return "";
                // next:
            }
        }

        queue<char> q;
        for (auto& [a, b] : in) {
            if (b == 0)
                q.push(a);
        }
        while (q.size()) {
            char t = q.front();
            ret += t;
            q.pop();
            for (auto& c : edges[t]) {
                in[c]--;
                if (in[c] == 0)
                    q.push(c);
            }
        }
        for (auto& [a, b] : in) {
            if (b != 0)
                return "";
        }
        // cout << ret;
        return ret;
    }
};